class Solution
{
public:
    int maxSumMinProduct(vector<int> &nums)
    {
        int n = nums.size();
        vector<long long> prefixSum(n + 1, 0);
        for (int i = 0; i < n; ++i)
        {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        vector<int> lastLessIndex(n);
        vector<int> nextLessIndex(n);
        stack<int> s;
        for (int i = 0; i < n; ++i)
        {
            while (!s.empty())
            {
                if (nums[s.top()] >= nums[i])
                {
                    s.pop();
                }
                else
                {
                    break;
                }
            }
            if (s.empty())
            {
                lastLessIndex[i] = -1;
            }
            else
            {
                lastLessIndex[i] = s.top();
            }
            s.push(i);
        }
        s = stack<int>();
        for (int i = n - 1; i >= 0; --i)
        {
            while (!s.empty())
            {
                if (nums[s.top()] >= nums[i])
                {
                    s.pop();
                }
                else
                {
                    break;
                }
            }
            if (s.empty())
            {
                nextLessIndex[i] = n;
            }
            else
            {
                nextLessIndex[i] = s.top();
            }
            s.push(i);
        }
        long long maxProduct = 0;
        for (int i = 0; i < n; ++i)
        {
            long long product = static_cast<long long>(nums[i]) * (prefixSum[nextLessIndex[i]] - prefixSum[lastLessIndex[i] + 1]);
            maxProduct = max(maxProduct, product);
        }
        maxProduct %= 1000000007;
        return maxProduct;
    }
};